{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #寻宝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #breadth-first-search #array #dynamic-programming #bitmask #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #广度优先搜索 #数组 #动态规划 #状态压缩 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimalSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻宝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。</p>\n",
    "\n",
    "<p>迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 &#39;S&#39; 表示），和唯一的宝藏地点（用 &#39;T&#39; 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 &#39;M&#39; 表示），<strong>只有所有机关均被触发，才可以拿到宝藏。</strong></p>\n",
    "\n",
    "<p>要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 &#39;O&#39; 表示），每个石堆都有<strong>无限</strong>个足够触发机关的重石。但是由于石头太重，我们一次只能搬<strong>一个</strong>石头到指定地点。</p>\n",
    "\n",
    "<p>迷宫中同样有一些墙壁（用 &#39;#&#39; 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 &#39;.&#39; 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。</p>\n",
    "\n",
    "<p>我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： [&quot;S#O&quot;, &quot;M..&quot;, &quot;M.T&quot;]</p>\n",
    "\n",
    "<p>输出：16</p>\n",
    "\n",
    "<p>解释：最优路线为： S-&gt;O, cost = 4, 去搬石头 O-&gt;第二行的M, cost = 3, M机关触发 第二行的M-&gt;O, cost = 3, 我们需要继续回去 O 搬石头。 O-&gt;第三行的M, cost = 4, 此时所有机关均触发 第三行的M-&gt;T, cost = 2，去T点拿宝藏。 总步数为16。 <img alt=\"图片.gif\" src=\"https://pic.leetcode-cn.com/6bfff669ad65d494cdc237bcedfec10a2b1ac2f2593c2bf97e9aecb41dc8a08b-%E5%9B%BE%E7%89%87.gif\" /></p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： [&quot;S#O&quot;, &quot;M.#&quot;, &quot;M.T&quot;]</p>\n",
    "\n",
    "<p>输出：-1</p>\n",
    "\n",
    "<p>解释：我们无法搬到石头触发机关</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入： [&quot;S#O&quot;, &quot;M.T&quot;, &quot;M..&quot;]</p>\n",
    "\n",
    "<p>输出：17</p>\n",
    "\n",
    "<p>解释：注意终点也是可以通行的。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= maze.length&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= maze[i].length&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>maze[i].length == maze[j].length</code></li>\n",
    "\t<li>S 和 T 有且只有一个</li>\n",
    "\t<li>0 &lt;= M的数量 &lt;= 16</li>\n",
    "\t<li>0 &lt;= O的数量 &lt;= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xun-bao](https://leetcode.cn/problems/xun-bao/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xun-bao](https://leetcode.cn/problems/xun-bao/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"S#O\", \"M..\", \"M.T\"]', '[\"S#O\", \"M.#\", \"M.T\"]', '[\"S#O\", \"M.T\", \"M..\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def minimalSteps(self, maze: List[str]) -> int:\n",
    "        # 四个方向\n",
    "        dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "\n",
    "        # 计算（x, y）到maze中其他点的距离，结果保存在ret中\n",
    "        def bfs(x, y, maze, m, n):\n",
    "            ret = [[-1]*n for _ in range(m)]\n",
    "            ret[x][y] = 0\n",
    "            q = Queue()\n",
    "            q.put((x,y))\n",
    "            while q.qsize():\n",
    "                curx, cury = q.get()\n",
    "                for dx, dy in dd:\n",
    "                    nx = curx + dx\n",
    "                    ny = cury + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and ret[nx][ny] == -1:\n",
    "                        ret[nx][ny] = ret[curx][cury] + 1\n",
    "                        q.put((nx, ny))\n",
    "            return ret\n",
    "\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "\n",
    "        startX = -1\n",
    "        startY = -1\n",
    "        endX = -1\n",
    "        endY = -1\n",
    "\n",
    "        # 机关 & 石头\n",
    "        buttons = []\n",
    "        stones = []\n",
    "\n",
    "        # 记录所有特殊信息的位置\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if maze[i][j] == 'S':\n",
    "                    startX = i\n",
    "                    startY = j\n",
    "                elif maze[i][j] == 'T':\n",
    "                    endX = i\n",
    "                    endY = j\n",
    "                elif maze[i][j] == 'O':\n",
    "                    stones.append((i,j))\n",
    "                elif maze[i][j] == 'M':\n",
    "                    buttons.append((i,j))\n",
    "                else:\n",
    "                    pass\n",
    "        \n",
    "        nb = len(buttons)\n",
    "        ns = len(stones)\n",
    "\n",
    "        startToAnyPos = bfs(startX, startY, maze, m, n)\n",
    "\n",
    "        # 若没有机关，最短距离就是(startX, startY)到(endX, endY)的距离\n",
    "        if nb == 0:\n",
    "            return startToAnyPos[endX][endY]\n",
    "\n",
    "        # 记录第i个机关到第j个机关的最短距离\n",
    "        # dist[i][nb]表示到起点的距离， dist[i][nb+1]表示到终点的距离\n",
    "        dist = [[-1]*(nb+2) for _ in range(nb)]\n",
    "\n",
    "        # 遍历所有机关，计算其和其他点的距离\n",
    "        buttonsToAnyPos = []\n",
    "        for i in range(nb):\n",
    "            bx, by = buttons[i]\n",
    "            # 记录第i个机关到其他点的距离\n",
    "            iToAnyPos = bfs(bx, by, maze, m, n)\n",
    "            buttonsToAnyPos.append(iToAnyPos)\n",
    "            # 第i个机关到终点的距离就是(bx, by)到(endX, endY)的距离\n",
    "            dist[i][nb + 1] = iToAnyPos[endX][endY]\n",
    "        \n",
    "        for i in range(nb):\n",
    "            # 计算第i个机关到(startX, startY)的距离\n",
    "            # 即从第i个机关出发，通过每个石头(sx, sy)，到(startX, startY)的最短距离\n",
    "            tmp = -1\n",
    "            for j in range(ns):\n",
    "                sx, sy = stones[j]\n",
    "                if buttonsToAnyPos[i][sx][sy] != -1 and startToAnyPos[sx][sy] != -1:\n",
    "                    if tmp == -1 or tmp > buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]:\n",
    "                        tmp = buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]\n",
    "\n",
    "            dist[i][nb] = tmp\n",
    "\n",
    "            # 计算第i个机关到第j个机关的距离\n",
    "            # 即从第i个机关出发，通过每个石头(sx, sy)，到第j个机关的最短距离\n",
    "            for j in range(i+1, nb):\n",
    "                mn = -1\n",
    "                for k in range(ns):\n",
    "                    sx, sy = stones[k]\n",
    "                    if buttonsToAnyPos[i][sx][sy] != -1 and buttonsToAnyPos[j][sx][sy] != -1:\n",
    "                        if mn == -1 or mn > buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]:\n",
    "                            mn = buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]\n",
    "                # 距离是无向图，对称的\n",
    "                dist[i][j] = mn\n",
    "                dist[j][i] = mn\n",
    "        \n",
    "        # 若有任意一个机关 到起点或终点没有路径(即为-1),则说明无法达成，返回-1\n",
    "        for i in range(nb):\n",
    "            if dist[i][nb] == -1 or dist[i][nb+1] == -1:\n",
    "                return -1\n",
    "        \n",
    "        # dp数组， -1代表没有遍历到, 1<<nb表示题解中提到的mask, dp[mask][j]表示当前处于第j个机关，总的触发状态为mask所需要的最短路径, 由于有2**nb个状态，因此1<<nb的开销必不可少\n",
    "        dp = [[-1]*nb for _ in range(1 << nb)]\n",
    "        # 初识状态，即从start到第i个机关，此时mask的第i位为1，其余位为0\n",
    "        for i in range(nb):\n",
    "            dp[1 << i][i] = dist[i][nb]\n",
    "        \n",
    "        # 二进制中数字大的mask的状态肯定比数字小的mask的状态多，所以直接从小到大遍历更新即可\n",
    "        for mask in range(1, (1 << nb)):\n",
    "            for i in range(nb):\n",
    "                # 若当前位置是正确的，即mask的第i位是1\n",
    "                if mask & (1 << i) != 0:\n",
    "                    for j in range(nb):\n",
    "                        # 选择下一个机关j,要使得机关j目前没有到达，即mask的第j位是0\n",
    "                        if mask & (1 << j) == 0:\n",
    "                            nextMask = mask | (1 << j)\n",
    "                            if dp[nextMask][j] == -1 or dp[nextMask][j] > dp[mask][i] + dist[i][j]:\n",
    "                                dp[nextMask][j] = dp[mask][i] + dist[i][j]\n",
    "\n",
    "        # 最后一个机关到终点\n",
    "        ans = -1\n",
    "        finalMask = (1 << nb) - 1\n",
    "        for i in range(nb):\n",
    "            if ans == -1 or ans > dp[finalMask][i] + dist[i][nb + 1]:\n",
    "                ans = dp[finalMask][i] + dist[i][nb + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def minimalSteps(self, maze: List[str]) -> int:\n",
    "        # 四个方向\n",
    "        dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "\n",
    "        # 计算（x, y）到maze中其他点的距离，结果保存在ret中\n",
    "        def bfs(x, y, maze, m, n):\n",
    "            ret = [[-1]*n for _ in range(m)]\n",
    "            ret[x][y] = 0\n",
    "            q = Queue()\n",
    "            q.put((x,y))\n",
    "            while q.qsize():\n",
    "                curx, cury = q.get()\n",
    "                for dx, dy in dd:\n",
    "                    nx = curx + dx\n",
    "                    ny = cury + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and ret[nx][ny] == -1:\n",
    "                        ret[nx][ny] = ret[curx][cury] + 1\n",
    "                        q.put((nx, ny))\n",
    "            return ret\n",
    "\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "\n",
    "        startX = -1\n",
    "        startY = -1\n",
    "        endX = -1\n",
    "        endY = -1\n",
    "\n",
    "        # 机关 & 石头\n",
    "        buttons = []\n",
    "        stones = []\n",
    "\n",
    "        # 记录所有特殊信息的位置\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if maze[i][j] == 'S':\n",
    "                    startX = i\n",
    "                    startY = j\n",
    "                elif maze[i][j] == 'T':\n",
    "                    endX = i\n",
    "                    endY = j\n",
    "                elif maze[i][j] == 'O':\n",
    "                    stones.append((i,j))\n",
    "                elif maze[i][j] == 'M':\n",
    "                    buttons.append((i,j))\n",
    "                else:\n",
    "                    pass\n",
    "        \n",
    "        nb = len(buttons)\n",
    "        ns = len(stones)\n",
    "\n",
    "        startToAnyPos = bfs(startX, startY, maze, m, n)\n",
    "\n",
    "        # 若没有机关，最短距离就是(startX, startY)到(endX, endY)的距离\n",
    "        if nb == 0:\n",
    "            return startToAnyPos[endX][endY]\n",
    "\n",
    "        # 记录第i个机关到第j个机关的最短距离\n",
    "        # dist[i][nb]表示到起点的距离， dist[i][nb+1]表示到终点的距离\n",
    "        dist = [[-1]*(nb+2) for _ in range(nb)]\n",
    "\n",
    "        # 遍历所有机关，计算其和其他点的距离\n",
    "        buttonsToAnyPos = []\n",
    "        for i in range(nb):\n",
    "            bx, by = buttons[i]\n",
    "            # 记录第i个机关到其他点的距离\n",
    "            iToAnyPos = bfs(bx, by, maze, m, n)\n",
    "            buttonsToAnyPos.append(iToAnyPos)\n",
    "            # 第i个机关到终点的距离就是(bx, by)到(endX, endY)的距离\n",
    "            dist[i][nb + 1] = iToAnyPos[endX][endY]\n",
    "        \n",
    "        for i in range(nb):\n",
    "            # 计算第i个机关到(startX, startY)的距离\n",
    "            # 即从第i个机关出发，通过每个石头(sx, sy)，到(startX, startY)的最短距离\n",
    "            tmp = -1\n",
    "            for j in range(ns):\n",
    "                sx, sy = stones[j]\n",
    "                if buttonsToAnyPos[i][sx][sy] != -1 and startToAnyPos[sx][sy] != -1:\n",
    "                    if tmp == -1 or tmp > buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]:\n",
    "                        tmp = buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]\n",
    "\n",
    "            dist[i][nb] = tmp\n",
    "\n",
    "            # 计算第i个机关到第j个机关的距离\n",
    "            # 即从第i个机关出发，通过每个石头(sx, sy)，到第j个机关的最短距离\n",
    "            for j in range(i+1, nb):\n",
    "                mn = -1\n",
    "                for k in range(ns):\n",
    "                    sx, sy = stones[k]\n",
    "                    if buttonsToAnyPos[i][sx][sy] != -1 and buttonsToAnyPos[j][sx][sy] != -1:\n",
    "                        if mn == -1 or mn > buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]:\n",
    "                            mn = buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]\n",
    "                # 距离是无向图，对称的\n",
    "                dist[i][j] = mn\n",
    "                dist[j][i] = mn\n",
    "        \n",
    "        # 若有任意一个机关 到起点或终点没有路径(即为-1),则说明无法达成，返回-1\n",
    "        for i in range(nb):\n",
    "            if dist[i][nb] == -1 or dist[i][nb+1] == -1:\n",
    "                return -1\n",
    "        \n",
    "        # dp数组， -1代表没有遍历到, 1<<nb表示题解中提到的mask, dp[mask][j]表示当前处于第j个机关，总的触发状态为mask所需要的最短路径, 由于有2**nb个状态，因此1<<nb的开销必不可少\n",
    "        dp = [[-1]*nb for _ in range(1 << nb)]\n",
    "        # 初识状态，即从start到第i个机关，此时mask的第i位为1，其余位为0\n",
    "        for i in range(nb):\n",
    "            dp[1 << i][i] = dist[i][nb]\n",
    "        \n",
    "        # 二进制中数字大的mask的状态肯定比数字小的mask的状态多，所以直接从小到大遍历更新即可\n",
    "        for mask in range(1, (1 << nb)):\n",
    "            for i in range(nb):\n",
    "                # 若当前位置是正确的，即mask的第i位是1\n",
    "                if mask & (1 << i) != 0:\n",
    "                    for j in range(nb):\n",
    "                        # 选择下一个机关j,要使得机关j目前没有到达，即mask的第j位是0\n",
    "                        if mask & (1 << j) == 0:\n",
    "                            nextMask = mask | (1 << j)\n",
    "                            if dp[nextMask][j] == -1 or dp[nextMask][j] > dp[mask][i] + dist[i][j]:\n",
    "                                dp[nextMask][j] = dp[mask][i] + dist[i][j]\n",
    "\n",
    "        # 最后一个机关到终点\n",
    "        ans = -1\n",
    "        finalMask = (1 << nb) - 1\n",
    "        for i in range(nb):\n",
    "            if ans == -1 or ans > dp[finalMask][i] + dist[i][nb + 1]:\n",
    "                ans = dp[finalMask][i] + dist[i][nb + 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maze = None\n",
    "        self.dist_m2stone = None\n",
    "        self.num2ms = {}\n",
    "        self.dp = None\n",
    "        self.min_dist_between_ms = None\n",
    "        self.dist_m2target = None\n",
    "\n",
    "    def minimalSteps(self, maze: List[str]) -> int:\n",
    "        self.maze = maze\n",
    "        m_idx = 1\n",
    "        stones = []\n",
    "        target = []\n",
    "        for i, line in enumerate(maze):\n",
    "            for j in range(len(line)):\n",
    "                point = line[j]\n",
    "                if point == 'S':\n",
    "                    self.num2ms[self.get_num(i, j)] = 0\n",
    "                elif point == 'M':\n",
    "                    self.num2ms[self.get_num(i, j)] = m_idx\n",
    "                    m_idx += 1\n",
    "                elif point == 'O':\n",
    "                    stones.append([i, j])\n",
    "                elif point == 'T':\n",
    "                    target = [i, j]\n",
    "\n",
    "        self.dist_m2stone = [[math.inf for _ in range(len(stones))] for _ in range(len(self.num2ms))]\n",
    "        for i, [i0, j0] in enumerate(stones):\n",
    "            self.bfs(i0, j0, [[False for _ in range(len(maze[0]))] for _ in range(len(maze))], i)\n",
    "\n",
    "        self.dist_m2target = [math.inf for _ in range(len(self.num2ms))]\n",
    "        self.bfs_2(target[0], target[1], [[False for _ in range(len(maze[0]))] for _ in range(len(maze))])\n",
    "\n",
    "        self.min_dist_between_ms = [[0 for _ in range(len(self.num2ms))] for _ in range(len(self.num2ms))]\n",
    "        for i in range(len(self.num2ms)):\n",
    "            for j in range(i + 1, len(self.num2ms)):\n",
    "                min_dist = math.inf\n",
    "                for k in range(len(stones)):\n",
    "                    min_dist = min(min_dist, self.dist_m2stone[i][k] + self.dist_m2stone[j][k])\n",
    "                self.min_dist_between_ms[i][j] = min_dist\n",
    "                self.min_dist_between_ms[j][i] = min_dist\n",
    "\n",
    "        self.dp = [[-1 for _ in range(len(self.num2ms))] for _ in range(1 << (len(self.num2ms) - 1))]\n",
    "        if len(self.num2ms) > 1:\n",
    "            res = min([self.dfs((1 << (len(self.num2ms) - 1)) - 1, last_m) + self.dist_m2target[last_m] for last_m in\n",
    "                       range(1, len(self.num2ms))])\n",
    "        else:\n",
    "            res = self.dist_m2target[0]\n",
    "        if res == math.inf:\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "    def dfs(self, state, last_m):\n",
    "        if self.dp[state][last_m] >= 0:\n",
    "            return self.dp[state][last_m]\n",
    "        reserved_state = state\n",
    "        state = state ^ (1 << (len(self.num2ms) - last_m - 1))\n",
    "        if state == 0:\n",
    "            dist = self.min_dist_between_ms[0][last_m]\n",
    "        else:\n",
    "            dist = math.inf\n",
    "            for last_m_now in range(1, len(self.num2ms)):\n",
    "                if (state & (1 << (len(self.num2ms) - last_m_now - 1))) > 0:\n",
    "                    dist = min(dist, self.dfs(state, last_m_now) + self.min_dist_between_ms[last_m][last_m_now])\n",
    "        self.dp[reserved_state][last_m] = dist\n",
    "        return dist\n",
    "\n",
    "    def bfs_2(self, i, j, visited):\n",
    "        q = deque()\n",
    "        q.append([i, j, 0])\n",
    "        while len(q) > 0:\n",
    "            [i, j, step] = q.popleft()\n",
    "            if i < 0 or i >= len(self.maze) or j < 0 or j >= len(self.maze[0]) or visited[i][j] or \\\n",
    "                    self.maze[i][j] == '#':\n",
    "                continue\n",
    "            visited[i][j] = True\n",
    "            if self.maze[i][j] == 'S' or self.maze[i][j] == 'M':\n",
    "                self.dist_m2target[self.num2ms[self.get_num(i, j)]] = step\n",
    "            q.append([i - 1, j, step + 1])\n",
    "            q.append([i + 1, j, step + 1])\n",
    "            q.append([i, j - 1, step + 1])\n",
    "            q.append([i, j + 1, step + 1])\n",
    "\n",
    "    def bfs(self, i, j, visited, stone_idx):\n",
    "        q = deque()\n",
    "        q.append([i, j, 0])\n",
    "        while len(q) > 0:\n",
    "            [i, j, step] = q.popleft()\n",
    "            if i < 0 or i >= len(self.maze) or j < 0 or j >= len(self.maze[0]) or visited[i][j] or \\\n",
    "                    self.maze[i][j] == '#':\n",
    "                continue\n",
    "            visited[i][j] = True\n",
    "            if self.maze[i][j] == 'S' or self.maze[i][j] == 'M':\n",
    "                self.dist_m2stone[self.num2ms[self.get_num(i, j)]][stone_idx] = step\n",
    "            q.append([i - 1, j, step + 1])\n",
    "            q.append([i + 1, j, step + 1])\n",
    "            q.append([i, j - 1, step + 1])\n",
    "            q.append([i, j + 1, step + 1])\n",
    "\n",
    "    def get_num(self, i, j):\n",
    "        return i * len(self.maze[0]) + j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minimalSteps(self, maze: List[str]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        def bfs(sr, sc):\n",
    "            dis = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "            dis[sr][sc] = 0\n",
    "            queue = collections.deque([[sr, sc]])\n",
    "            while queue:\n",
    "                i, j = queue.popleft()\n",
    "                for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < m and 0 <= y < n and maze[x][y] != '#' and dis[x][y] > dis[i][j] + 1:\n",
    "                        dis[x][y] = dis[i][j] + 1 \n",
    "                        queue.append([x, y])\n",
    "            return dis \n",
    "        stone = []\n",
    "        button = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if maze[i][j] == 'S':\n",
    "                    sr, sc = i, j\n",
    "                if maze[i][j] == 'T':\n",
    "                    dr, dc = i, j \n",
    "                if maze[i][j] == 'O':\n",
    "                    stone.append([i, j])\n",
    "                if maze[i][j] == 'M':\n",
    "                    button.append([i, j])\n",
    "        startDis = bfs(sr, sc)\n",
    "        ns, nb = len(stone), len(button)\n",
    "        if not nb:\n",
    "            return startDis[dr][dc] if startDis[dr][dc] != float('inf') else - 1\n",
    "        dis = [[float('inf') for _ in range(nb + 2)] for _ in range(nb)]\n",
    "        disSum = []\n",
    "        for i in range(nb):\n",
    "            curDis = bfs(button[i][0], button[i][1])\n",
    "            dis[i][-1] = curDis[dr][dc]\n",
    "            disSum.append(curDis)\n",
    "        for i in range(nb):\n",
    "            for j in range(i + 1, nb):\n",
    "                for k in range(ns):\n",
    "                    if disSum[i][stone[k][0]][stone[k][1]] == float('inf') or disSum[j][stone[k][0]][stone[k][1]] == float('inf') or disSum[i][stone[k][0]][stone[k][1]] + disSum[j][stone[k][0]][stone[k][1]] >= dis[i][j]:\n",
    "                        continue\n",
    "                    dis[i][j] = dis[j][i] = disSum[i][stone[k][0]][stone[k][1]] + disSum[j][stone[k][0]][stone[k][1]]\n",
    "            for j in range(ns):\n",
    "                if disSum[i][stone[j][0]][stone[j][1]] == float('inf') or startDis[stone[j][0]][stone[j][1]] == float('inf') or disSum[i][stone[j][0]][stone[j][1]] + startDis[stone[j][0]][stone[j][1]] >= dis[i][nb]:\n",
    "                    continue\n",
    "                dis[i][nb] = disSum[i][stone[j][0]][stone[j][1]] + startDis[stone[j][0]][stone[j][1]]\n",
    "        print(dis)\n",
    "        m = 1 << nb\n",
    "        dp = [[float('inf') for _ in range(nb)] for _ in range(m)]\n",
    "        for i in range(nb):\n",
    "            dp[1 << i][i] = dis[i][nb]\n",
    "        for i in range(1, m):\n",
    "            for cur in range(nb):\n",
    "                if not i & 1 << cur:\n",
    "                    continue\n",
    "                for nxt in range(nb):\n",
    "                    if i & 1 << nxt:\n",
    "                        continue\n",
    "                    dp[i | (1 << nxt)][nxt] = min(dp[i | (1 << nxt)][nxt], dp[i][cur] + dis[cur][nxt])\n",
    "        res = float('inf')\n",
    "        for i in range(nb):\n",
    "            res = min(res, dp[-1][i] + dis[i][-1])\n",
    "        return res if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalSteps(self, maze: List[str]) -> int:\n",
    "        height, width = len(maze), len(maze[0])\n",
    "\n",
    "        start_x = start_y = end_x = end_y = -1\n",
    "        table = collections.defaultdict(list)\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if maze[i][j] == \"S\":\n",
    "                    start_x, start_y = i, j\n",
    "                elif maze[i][j] == \"T\":\n",
    "                    end_x, end_y = i, j\n",
    "                elif maze[i][j] == \"O\":\n",
    "                    table[\"O\"].append((i, j))\n",
    "                elif maze[i][j] == \"M\":\n",
    "                    table[\"M\"].append((i, j))\n",
    "        \n",
    "        dist_s_to_o = collections.defaultdict(lambda: float('inf')) # {pos2:dist, pos3:dist}\n",
    "        dist_s_to_t = -1\n",
    "        dist_m_to_o = collections.defaultdict(lambda: collections.defaultdict(lambda: float('inf'))) # {pos1: {pos2:dist, pos3:dist}}\n",
    "        dist_m_to_t = collections.defaultdict(lambda: float('inf')) # {pos2:dist, pos3:dist}\n",
    "\n",
    "        # O(10**4) bfs s => find o, find t\n",
    "        que = [(start_x, start_y)]\n",
    "        visited_set = set()\n",
    "        visited_set.add((start_x, start_y))\n",
    "        step = 1\n",
    "        while que:\n",
    "            que2 = []\n",
    "            for x, y in que:\n",
    "                for _x, _y in [x-1,y],[x+1,y],[x,y-1],[x,y+1]:\n",
    "                    if not (0 <= _x < height and 0 <= _y < width) or maze[_x][_y] == \"#\":\n",
    "                        continue\n",
    "    \n",
    "                    if (_x, _y) in visited_set:\n",
    "                        continue\n",
    "\n",
    "                    if maze[_x][_y] == \"O\":\n",
    "                        dist_s_to_o[_x, _y] = step\n",
    "                    if maze[_x][_y] == \"T\":\n",
    "                        dist_s_to_t = step\n",
    "                    \n",
    "                    que2.append((_x, _y))\n",
    "                    visited_set.add((_x, _y))\n",
    "            step += 1\n",
    "            que = que2\n",
    "\n",
    "        # O(1.6 * 10**5) bfs M => find o, find t\n",
    "        for m_x, m_y in table[\"M\"]:\n",
    "            que = [(m_x, m_y)]\n",
    "            visited_set = set()\n",
    "            visited_set.add((m_x, m_y))\n",
    "            step = 1\n",
    "            while que:\n",
    "                que2 = []\n",
    "                for x, y in que:\n",
    "                    for _x, _y in [x-1,y],[x+1,y],[x,y-1],[x,y+1]:\n",
    "                        if not (0 <= _x < height and 0 <= _y < width) or maze[_x][_y] == \"#\":\n",
    "                            continue\n",
    "        \n",
    "                        if (_x, _y) in visited_set:\n",
    "                            continue\n",
    "\n",
    "                        if maze[_x][_y] == \"O\":\n",
    "                            dist_m_to_o[m_x, m_y][_x, _y] = step\n",
    "                        if maze[_x][_y] == \"T\":\n",
    "                            dist_m_to_t[m_x, m_y] = step\n",
    "                        \n",
    "                        que2.append((_x, _y))\n",
    "                        visited_set.add((_x, _y))\n",
    "                step += 1\n",
    "                que = que2\n",
    "        \n",
    "        # O(640) min dist = s -> o -> m'\n",
    "        dist_s_to_m = collections.defaultdict(lambda: float('inf')) # {pos2:dist, pos3:dist}\n",
    "        for m_x, m_y in table[\"M\"]:\n",
    "            min_dist = float('inf')\n",
    "            for stone_x, stone_y in table[\"O\"]:\n",
    "                min_dist = min(min_dist, dist_s_to_o[stone_x, stone_y] + dist_m_to_o[m_x, m_y][stone_x, stone_y])\n",
    "            dist_s_to_m[m_x, m_y] = min_dist\n",
    "        \n",
    "        # O(1.02 * 10**4) min dist = m -> o -> m'\n",
    "        dist_m_to_m = collections.defaultdict(lambda: collections.defaultdict(lambda: float('inf'))) # {pos1: {pos2:dist, pos3:dist}}\n",
    "        for i, (m_x, m_y) in enumerate(table[\"M\"]):\n",
    "            for j, (m_x_j, m_y_j) in enumerate(table[\"M\"]):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                min_dist = float('inf')\n",
    "                for stone_x, stone_y in table[\"O\"]:\n",
    "                    min_dist = min(min_dist, dist_m_to_o[m_x, m_y][stone_x, stone_y] + dist_m_to_o[m_x_j, m_y_j][stone_x, stone_y])\n",
    "                dist_m_to_m[m_x, m_y][m_x_j, m_y_j] = min_dist\n",
    "        \n",
    "        # if no m => return s -> t\n",
    "        if len(table[\"M\"]) == 0:\n",
    "            return dist_s_to_t\n",
    "\n",
    "        # O(1.67 * 10**7) recr => find ans\n",
    "        max_memo_number = pow(2, len(table[\"M\"])) - 1\n",
    "        @functools.lru_cache(None)\n",
    "        def recr(m_x, m_y, memo_m):\n",
    "            if memo_m == max_memo_number:\n",
    "                return dist_m_to_t[m_x, m_y]\n",
    "            \n",
    "            min_dist = float('inf')\n",
    "            for j, (m_x_j, m_y_j) in enumerate(table[\"M\"]):\n",
    "                if (1 << j) & memo_m > 0:\n",
    "                    continue\n",
    "                min_dist = min(min_dist, dist_m_to_m[m_x, m_y][m_x_j, m_y_j] + recr(m_x_j, m_y_j, memo_m | (1 << j)))\n",
    "            return min_dist\n",
    "\n",
    "        min_dist = float('inf')\n",
    "        for i, (m_x, m_y) in enumerate(table[\"M\"]):\n",
    "            min_dist = min(min_dist, dist_s_to_m[m_x, m_y] + recr(m_x, m_y, 1 << i))\n",
    "        return min_dist if min_dist < float('inf') else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
